// 39 组合总和
// https://leetcode.cn/problems/combination-sum/
// 回溯

/**
 * 
 * 示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：

输入: candidates = [2], target = 1
输出: []
 */

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
    // 本题应该使用回溯算法
    let res = backTracking(candidates, [], target, 0, []);

    if (res.length === 0) {
        console.log(
            `[combinationSum] NO answer for candidates ${JSON.stringify(
                candidates
            )} and target ${target}`
        );
    } else {
        console.log(
            `[combinationSum] ${res.length} answers for target ${target}`
        );

        for (let ans of res) {
            console.log(ans);
        }
    }

    return res;
};

var backTracking = function (
    remainInCandidates,
    curArr,
    target,
    level,
    finalCollector
) {
    if (remainInCandidates.length === 0) {
        return;
    }

    for (let i = level; i < remainInCandidates.length; i++) {
        curArr.push(remainInCandidates[i]);

        console.log(
            `[backtracking] testing ${JSON.stringify(
                curArr
            )}, target: ${target}`
        );

        const newTarget = target - remainInCandidates[i];
        if (newTarget === 0) {
            finalCollector.push([].concat(curArr));
            // 由于数组中默认所有数字都>0 已经找到当前解后，再往下递归(就是curArr不动)已经没有意义了，这里可以直接删除当前元素进入下一递归
            // 但如果数组中存在负数，那应该要继续往下递归
            console.log(`[backtracking] find answer`);
        } else if (newTarget > 0) {
            backTracking(
                remainInCandidates.slice(i),
                [].concat(curArr),
                newTarget,
                0,
                finalCollector
            );
        }

        curArr.splice(curArr.length - 1, 1);
    }

    return finalCollector;
};

// combinationSum([1, 2], 3);
// combinationSum([1, 2], 0);
// combinationSum([1], 3);
combinationSum([2, 3, 6, 7], 7);
// combinationSum([2, 3, 5], 8);
// combinationSum([8, 7, 4, 3], 11);
// combinationSum([4, 2, 8], 8);
